package InterviewTest.q1719_missingTwo;

import java.util.Arrays;

public class Solution_1 {
    /*
    最简单明了的方法 使用异或来解决 但是由于对数组进行了排序 所以时间复杂度为nlogn
    而要求为n 不符合时间要求
    首先确定两个指针p1 p2
    然后对排序后的数组 用两个指针依次异或 如果发现不等于0的代表这个位置缺失
     */
    public int[] missingTwo(int[] nums) {
        int miss1 = 0, miss2 = 0;
        int p1 = 1, p2 = 0;
        Arrays.sort(nums);
        while (p2 < nums.length) {
            if ((p1 ^ nums[p2]) != 0) {
                if (miss1 == 0) {
                    miss1 = p1;
                }else {
                    miss2 = p1;
                    break;
                }
                p1++;
                continue;
            }


            p1++;
            p2++;
        }

        if (miss1 == 0 && miss2 == 0) {
            return new int[]{nums.length + 1, nums.length + 2};
        }

        if (miss2 == 0) {
            return new int[]{miss1, nums[nums.length - 1] + 1};
        }

        return new int[]{miss1, miss2};
    }
}
